package org.source.code.collection.list.arrayList;

import org.cleaver.basic.annotations.Important;
import sun.misc.SharedSecrets;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.*;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

/**
 * JDK1.8之ArrayList源码分析
 * <p>
 * List接口的可调整大小的数组实现。实现所有可选的列表操作，并允许所有元素，包括 null。
 * 除了实现 List 接口之外，该类还提供了操作内部用于存储列表的数组大小的方法。（这个类大致相当于 Vector，只是它是不同步的。）
 * size、isEmpty、get、set、iterator 和 listIterator 操作以恒定时间运行。
 * add 操作在均摊常数时间中运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。
 * 与 LinkedList 实现相比，常量因子较低。每个ArrayList 实例都有一个容量。容量是用于存储列表中元素的数组的大小。
 * 它始终至少与列表大小一样大。随着元素被添加到 ArrayListSource，它的容量会自动增长。除了添加元素具有恒定的摊销时间成本之外，没有指定增长政策的细节。
 * 应用程序可以在使用 ensureCapacity 操作添加大量元素之前增加 ArrayListSource 实例的容量。这可以减少增量重新分配的量。
 * 注意这个实现不是同步的。如果多个线程同时访问一个ArrayList实例，并且至少有一个线程在结构上修改了列表，它必须< i> 在外部同步。
 * （结构修改是添加或删除一个或多个元素，或显式调整后备数组大小的任何操作；仅设置元素的值不是结构修改。）这通常是通过同步一些自然封装的对象来实现的列表。
 * 如果不存在此类对象，则应使用Collections.synchronizedList方法“包装”该列表。
 * 这最好在创建时完成，以防止对列表的意外不同步访问： List list = Collections.synchronizedList(new ArrayListSource(...));
 *
 * @author LiKun
 * @date 2021/10/19 10:47
 */
public class ArrayListSource<E> extends AbstractListSource<E>
        implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始容量(未指定初始容量时的默认容量)
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例(空数组实现，用于初始化数组)
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 要分配的数组的最大大小。一些 VM 在数组中保留一些头字。尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超出 VM 限制
     * 注：此处的大小之所以为{}是因为数组对象需要 8byte 大小数据位标识其相关信息(如：数组长度等元数据信息)
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 用于默认大小的空实例的共享空数组实例。将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayListSource 的元素存储在其中的数组缓冲区。 ArrayListSource 的容量就是这个数组缓冲区的长度。
     * 添加第一个元素时，任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayListSource 都将扩展为 DEFAULT_CAPACITY
     */
    transient Object[] elementData;                                       // 非私有以简化嵌套类访问

    /**
     * ArrayListSource 的大小（它包含的元素数）
     */
    private int size;

    /**
     * 构造一个初始容量为 10 的空列表
     */
    public ArrayListSource() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造一个具有指定初始容量的空列表
     *
     * @param initialCapacity 列表的初始容量
     *
     * @throws IllegalArgumentException 如果指定的初始容量为负
     */
    public ArrayListSource(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }

    /**
     * 构造一个包含指定集合元素的列表，按照集合的迭代器返回的顺序
     *
     * @param collection 其元素将被放入此列表的集合
     *
     * @throws NullPointerException 如果指定的集合为空
     */
    public ArrayListSource(Collection<? extends E> collection) {
        Object[] array = collection.toArray();                  // ArrayList.toArray 会生成新的数组，与 elementData 的数据相同但不是同一个对象

        if ((size = array.length) != 0) {
            if (collection.getClass() == ArrayListSource.class) {
                elementData = array;
            } else {
                elementData = Arrays.copyOf(array, size, Object[].class);
            }
        } else {
            // 替换为空数组
            elementData = EMPTY_ELEMENTDATA;
        }
    }

    /**
     * 计算容量；如果初始化时没有设置容量，则返回Math.max(DEFAULT_CAPACITY, minCapacity)，否则返回给定的容量
     *
     * @param elementData ArrayList的内部实现数组
     * @param minCapacity 给定的容量
     *
     * @return 根据情况返回容量
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    /**
     * 判断处理所需的最小容量是否超出界限并返回支持的最大容量
     *
     * @param minCapacity 所需的最小容量
     *
     * @return 处理后的容量
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {                                          // 溢出
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0) {
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        }
        if (toIndex > size) {
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        }
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
    }

    /**
     * 将此 ArrayListSource 实例的容量修剪为列表的当前大小。
     * 应用程序可以使用此操作来最小化 ArrayListSource 实例的存储。
     */
    public void trimToSize() {
        modCount++;                                                   // 此列表被结构修改的次数
        if (size < elementData.length) {
            elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 主动控制ArrayList增加容量，在某些情况下(插入大量数组)可以提高效率
     * 如有必要，增加此 ArrayListSource 实例的容量，以确保它至少可以容纳由最小容量参数指定的元素数量。
     *
     * @param minCapacity 所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            this.ensureExplicitCapacity(minCapacity);                                 // 计算容量并判断是否需要扩容
        }
    }

    /**
     * 将指定的元素附加到此列表的末尾。
     *
     * @param element 要附加到此列表的元素
     *
     * @return true (由 {@link Collection#add} 指定)
     */
    @Override
    public boolean add(E element) {
        // 计算并比较是否需要扩充容量，如果需要则扩充容量
        ensureCapacityInternal(size + 1);                        // 增加 modCount ！！
        elementData[size++] = element;
        return true;
    }

    /**
     * 在此列表中的指定位置插入指定元素。将当前在该位置的元素（如果有）和任何后续元素向右移动（向它们的索引添加一个）。
     *
     * @param index   要插入指定元素的索引
     * @param element 要插入的元素
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);                                   // 检查索引是否越界
        ensureCapacityInternal(size + 1);               // 增加 modCount ！！
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    /**
     * 判断容量是否需要扩容，如果需要则进行扩容
     *
     * @param minCapacity 需要的最小容量
     */
    @Important
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;                                                     // 此列表被结构修改的次数
        // 溢出意识代码；判断是否需要扩容
        if (minCapacity > elementData.length) {
            this.grow(minCapacity);                                          // 底层扩容方法
        }
    }

    /**
     * 计算容量并判断容量是否需要扩容，如果需要则进行扩容
     *
     * @param minCapacity 需要的最小容量
     */
    private void ensureCapacityInternal(int minCapacity) {
        this.ensureExplicitCapacity(ArrayListSource.calculateCapacity(elementData, minCapacity));
    }

    /**
     * 进入该方法表明 minCapacity > elementData.length
     * 增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。
     *
     * @param minCapacity 所需的最小容量
     */
    @Important
    private void grow(int minCapacity) {
        // 溢出意识代码
        int oldCapacity = elementData.length;
        // 将新容量设置为之前容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 判断扩容后的容量是否大于所需的最小容量
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        // 判断最新的容量是否超出界限；如果超出界限则根据 minCapacity 设置 newCapacity 的值
        if (newCapacity > MAX_ARRAY_SIZE) {
            newCapacity = ArrayListSource.hugeCapacity(minCapacity);
        }
        // minCapacity 通常接近 size，所以这是一个胜利
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 返回此列表中的元素数。
     *
     * @return 此列表中的元素数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 如果此列表不包含任何元素，则返回 true。
     *
     * @return 如果此列表不包含任何元素，则为 true
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 如果此列表包含指定的元素，则返回 true。更正式地说，当且仅当此列表包含至少一个元素 e 使得 (obj==null ? e==null : obj.equals(e)) 时，才返回 true。
     *
     * @param obj 要测试其在此列表中是否存在的元素
     *
     * @return 如果此列表包含指定的元素，则为 true
     */
    @Override
    public boolean contains(Object obj) {
        return indexOf(obj) >= 0;
    }

    /**
     * 返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。更正式地说，
     * 返回最低索引 i 使得 (o==null ? get(i)==null : o.equals(get(i)))，如果没有这样的索引，则返回 -1 .
     *
     * @param obj 要测试其在此列表中是否存在的元素
     */
    @Override
    public int indexOf(Object obj) {
        if (obj == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (obj.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1。更正式地，
     * 返回最高索引 i 使得 (o==null ? get(i)==null : o.equals(get(i)))，如果没有这样的索引，则返回 -1 .
     *
     * @param obj 要测试其在此列表中是否存在的元素
     */
    @Override
    public int lastIndexOf(Object obj) {
        if (obj == null) {
            for (int i = size - 1; i >= 0; i--) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (obj.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 返回此 ArrayListSource 实例的浅表副本。 （元素本身不会被复制。）
     *
     * @return 此 ArrayListSource 实例的克隆
     */
    @Override
    public Object clone() {
        try {
            ArrayListSource<?> clone = (ArrayListSource<?>) super.clone();
            clone.elementData = Arrays.copyOf(elementData, size);
            clone.modCount = 0;
            return clone;
        } catch (CloneNotSupportedException e) {
            // 这不应该发生，因为我们是可克隆的
            throw new InternalError(e);
        }
    }

    /**
     * 以适当的顺序（从第一个元素到最后一个元素）返回一个包含此列表中所有元素的数组。 返回的数组将是“安全的”，因为此列表不维护对它的引用。
     * （换句话说，此方法必须分配一个新数组）。因此调用者可以自由地修改返回的数组。 此方法充当基于数组和基于集合的 API 之间的桥梁。
     *
     * @return 按适当顺序包含此列表中所有元素的数组
     */
    @Override
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 以适当的顺序（从第一个元素到最后一个元素）返回一个包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的类型。
     * 如果列表适合指定的数组，则在其中返回。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。
     * <p>
     * 如果列表适合指定的数组并有剩余空间
     * （即，数组的元素比列表多），数组中紧跟在集合末尾之后的元素被设置为 null。
     * （如果调用者知道列表不包含任何空元素，这对于确定列表的长度 only 很有用。）
     *
     * @param array 要存储列表元素的数组，如果它足够大；否则，将为此分配一个相同运行时类型的新数组。
     *
     * @return 包含列表元素的数组
     *
     * @throws ArrayStoreException  如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型
     * @throws NullPointerException 如果指定的数组为空
     */
    @Override
    public <T> T[] toArray(T[] array) {
        if (array.length < size) {
            return (T[]) Arrays.copyOf(elementData, size, array.getClass());
        } else {
            System.arraycopy(elementData, 0, array, 0, size);
            if (array.length > size) {
                array[size] = null;
            }
            return array;
        }
    }

    // 位置访问操作
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回此列表中指定位置的元素。
     *
     * @param index 要返回的元素的索引
     *
     * @return 此列表中指定位置的元素
     *
     * @throws IndexOutOfBoundsException 索引下标越界
     */
    @Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

    /**
     * 用指定的元素替换此列表中指定位置的元素。
     *
     * @param index   要替换的元素的索引
     * @param element 要存储在指定位置的元素
     *
     * @return 之前在指定位置的元素
     *
     * @throws IndexOutOfBoundsException 索引下标越界
     */
    @Override
    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
     * 移除此列表中指定位置的元素。
     * 将任何后续元素向左移动（从它们的索引中减去一个）。
     *
     * @param index 要删除的元素的索引
     *
     * @return 从列表中删除的元素
     *
     * @throws IndexOutOfBoundsException 索引下标越界
     */
    @Override
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;                                           // 明确让GC做它的工作

        return oldValue;
    }

    /**
     * 从此列表中删除第一次出现的指定元素（如果存在）。如果列表不包含该元素，则它保持不变。更正式地，删除具有最低索引 i 的元素，使得
     * (o==null ? get(i)==null : o.equals(get(i)))（如果存在这样的元素）。如果此列表包含指定的元素（或等效地，如果此列表因调用而更改），则返回 true。
     *
     * @param obj 要从此列表中删除的元素（如果存在）
     *
     * @return 如果此列表包含指定的元素，则为 true
     */
    @Override
    public boolean remove(Object obj) {
        if (obj == null) {
            for (int index = 0; index < size; index++) {
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
            }
        } else {
            for (int index = 0; index < size; index++) {
                if (obj.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
            }
        }
        return false;
    }

    /*
     * 跳过边界检查并且不返回删除的值的私有删除方法。
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);             // 移动数组中的数据
        }
        elementData[--size] = null;                                      // 明确让GC做它的工作
    }

    /**
     * 从此列表中删除所有元素。此调用返回后，列表将为空。
     */
    @Override
    public void clear() {
        modCount++;

        // 明确让GC做它的工作
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }

        size = 0;
    }

    /**
     * 按照指定集合的​​迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。如果在操作进行时修改了指定的集合，则此操作的行为未定义。
     * （这意味着如果指定的集合是这个列表，并且这个列表是非空的，那么这个调用的行为是未定义的。）
     *
     * @param coll 包含要添加到此列表的元素的集合
     *
     * @return 如果此列表因调用而更改，则为 true
     *
     * @throws NullPointerException 如果指定的集合为空
     */
    @Override
    public boolean addAll(Collection<? extends E> coll) {
        Object[] arr = coll.toArray();
        int numNew = arr.length;
        ensureCapacityInternal(size + numNew);                                   // 增加 modCount
        System.arraycopy(arr, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 从指定位置开始，将指定集合中的所有元素插入此列表。将当前在该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。
     * 新元素将按照指定集合的​​迭代器返回的顺序出现在列表中。
     *
     * @param index 从指定集合插入第一个元素的索引
     * @param coll  包含要添加到此列表的元素的集合
     *
     * @return 如果此列表因调用而更改，则为 true<tt>
     *
     * @throws IndexOutOfBoundsException 索引下标越界
     * @throws NullPointerException      如果指定的集合为空
     */
    @Override
    public boolean addAll(int index, Collection<? extends E> coll) {
        rangeCheckForAdd(index);

        Object[] a = coll.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);                             // 扩充容量

        int numMoved = size - index;
        if (numMoved > 0) {
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        }

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 从此列表中删除其索引介于 {@code fromIndex}（包含）和 {@code toIndex}（不包含）之间的所有元素。将任何后续元素向左移动（减少它们的索引）。
     * 此调用通过 {@code (toIndex - fromIndex)} 元素缩短列表。 （如果{@code toIndex==fromIndex}，则此操作无效。）
     *
     * @throws IndexOutOfBoundsException 如果 {@code fromIndex} 或 {@code toIndex} 超出范围
     *                                   （{@code fromIndex < 0 || fromIndex >= size() || toIndex > size() || toIndex <
     *                                   fromIndex}）
     */
    @Override
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);               // 移动数组中的数据

        // 明确让GC做它的工作
        int newSize = size - (toIndex - fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

    /**
     * 检查给定的索引是否在范围内。如果不是，则抛出适当的运行时异常。
     * 此方法不检查索引是否为负数：它始终在数组访问之前立即使用，如果索引为负数，则抛出 ArrayIndexOutOfBoundsException。
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    /**
     * add 和 addAll 使用的 rangeCheck 版本。
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }

    /**
     * 构造一个 IndexOutOfBoundsException 详细消息。在错误处理代码的许多可能重构中，这种“概述”在服务器和客户端 VM 上表现最佳。
     */
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    /**
     * 从此列表中删除包含在指定集合中的所有元素。
     *
     * @param coll 包含要从此列表中删除的元素的集合
     *
     * @return {@code true} 如果此列表因调用而更改
     *
     * @throws ClassCastException   if 此列表的元素的类与指定的集合不兼容
     * @throws NullPointerException 如果此列表包含空元素并且指定的集合不允许空元素，或者如果指定的集合为空
     * @see Collection#contains(Object)
     */
    @Override
    public boolean removeAll(Collection<?> coll) {
        Objects.requireNonNull(coll);
        return batchRemove(coll, false);
    }

    /**
     * 仅保留此列表中包含在指定集合中的元素。换句话说，从该列表中删除所有未包含在指定集合中的元素。
     *
     * @param coll 包含要保留在此列表中的元素的集合
     *
     * @return {@code true} 如果此列表因调用而更改
     *
     * @throws ClassCastException   如果此列表的元素的类与指定的集合不兼容
     * @throws NullPointerException 如果此列表包含空元素并且指定的集合不允许空元素或指定的集合为空
     * @see Collection#contains(Object)
     */
    @Override
    public boolean retainAll(Collection<?> coll) {
        Objects.requireNonNull(coll);
        return batchRemove(coll, true);
    }

    /**
     * 批量删除相关数据
     *
     * @param coll       给定的集合
     * @param complement complement ? 保留coll中的数据 : 删除coll中的数据
     *
     * @return 操作是否成功
     */
    private boolean batchRemove(Collection<?> coll, boolean complement) {
        int r = 0, w = 0;
        boolean modified = false;
        final Object[] elementData = this.elementData;
        try {
            for (; r < size; r++) {
                // 根据 complement 的值判断保留还是删除该数据；complement ? 保留coll中的数据 : 删除coll中的数据
                if (coll.contains(elementData[r]) == complement) {
                    elementData[w++] = elementData[r];
                }
            }
        } finally {
            // 保持与 AbstractCollection 的行为兼容性，即使 coll.contains() 抛出异常。
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;
            }
            if (w != size) {
                // 明确让GC做它的工作
                for (int i = w; i < size; i++) {
                    elementData[i] = null;
                }
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

    /**
     * 将 ArrayListSource 实例的状态保存到流中（即序列化它）。
     *
     * @serialData 支持 ArrayListSource 实例的数组的长度被发出（int），然后是它的所有元素（每个元素都是一个 Object）以正确的顺序。
     */
    private void writeObject(ObjectOutputStream s) throws IOException {
        // 写出元素计数和任何隐藏的东西
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // 写出大小作为与 clone() 的行为兼容性的容量
        s.writeInt(size);

        // 按正确的顺序写出所有元素。
        for (int i = 0; i < size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 从流中重构 ArrayListSource 实例（即反序列化它）。
     */
    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 阅读大小，以及任何隐藏的东西
        s.defaultReadObject();

        // 容量读取；ignore
        s.readInt();

        if (size > 0) {
            // 就像 clone()，根据大小而不是容量分配数组
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 按正确顺序读入所有元素。
            for (int i = 0; i < size; i++) {
                a[i] = s.readObject();
            }
        }
    }

    /**
     * 返回此列表中元素的列表迭代器（以适当的顺序），从列表中的指定位置开始。指定的索引指示初始调用 {@link ListIterator#next next} 将返回的第一个元素。
     * 对 {@link ListIterator#previous previous} 的初始调用将返回指定索引减一的元素。
     * <p>
     * 返回的列表迭代器是 fail-fast。
     *
     * @throws IndexOutOfBoundsException 索引下标越界
     */
    @Override
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index);
        }
        return new ListItr(index);
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence).
     * <p>
     * The returned list iterator is <a href="#fail-fast">fail-fast</i></a>.
     *
     * @see #listIterator(int)
     */
    @Override
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * Returns an iterator over the elements in this list in proper sequence.
     * <p>
     * The returned iterator is <a href="#fail-fast">fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * 返回此列表中指定的  fromIndex（包括）和 toIndex（不包括在内）之间的部分的视图。（如果 fromIndex 和 toIndex 相等，则返回列表为空。）
     * 返回列表由此列表支持，因此返回列表中的非结构性更改会反映在此列表中，反之亦然反之。返回的列表支持所有可选的列表操作。
     * <p>
     * 此方法消除了对显式范围操作（数组通常存在的排序）的需要。通过传递子列表视图而不是整个列表，任何需要列表的操作都可以用作范围操作。
     * 例如，以下习语从列表中删除一系列元素：
     * <p>
     * list.subList(from, to).clear();
     * </pre>
     * 可以为 {@link #indexOf(Object)} 和 {@link #lastIndexOf(Object)} 构造类似的习惯用法，
     * 并且 {@link Collections} 类中的所有算法都可以应用于子列表。
     * <p>
     * 如果支持列表（即此列表）以除返回列表以外的任何方式在结构上进行了修改，则此方法返回的列表的语义将变为未定义。
     * （结构修改是那些改变这个列表的大小，或者以其他方式扰乱它，以致正在进行的迭代可能会产生不正确的结果。）
     *
     * @param fromIndex 左边界索引(包含)
     * @param toIndex   右边界索引(不包含)
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws IllegalArgumentException  {@inheritDoc}
     */
    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        final int size = this.size;
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        final E[] elementData = (E[]) this.elementData;

        for (int i = 0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
     * list.
     * <p>
     * The {@code Spliterator} reports {@link Spliterator#SIZED},
     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
     * Overriding implementations should document the reporting of additional
     * characteristic values.
     *
     * @return a {@code Spliterator} over the elements in this list
     *
     * @since 1.8
     */
    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSource.ArrayListSpliterator<>(this, 0, -1, 0);
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // 找出要删除的元素；在此阶段从过滤谓词抛出的任何异常；将保持集合不变
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i = 0; modCount == expectedModCount && i < size; i++) {
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // 将幸存的元素移动到已删除元素留下的空间上
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k = newSize; k < size; k++) {
                elementData[k] = null;  // 让 gc 完成它的工作
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i = 0; modCount == expectedModCount && i < size; i++) {
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    @Override
    public void sort(Comparator<? super E> comparator) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, comparator);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    /**
     * Index-based split-by-two, lazily initialized Spliterator
     */
    static final class ArrayListSpliterator<E> implements Spliterator<E> {

        /*
         * If ArrayLists were immutable, or structurally immutable (no
         * adds, removes, etc), we could implement their spliterators
         * with Arrays.spliterator. Instead we detect as much
         * interference during traversal as practical without
         * sacrificing much performance. We rely primarily on
         * modCounts. These are not guaranteed to detect concurrency
         * violations, and are sometimes overly conservative about
         * within-thread interference, but detect enough problems to
         * be worthwhile in practice. To carry this out, we (1) lazily
         * initialize fence and expectedModCount until the latest
         * point that we need to commit to the state we are checking
         * against; thus improving precision.  (This doesn't apply to
         * SubLists, that create spliterators with current non-lazy
         * values).  (2) We perform only a single
         * ConcurrentModificationException check at the end of forEach
         * (the most performance-sensitive method). When using forEach
         * (as opposed to iterators), we can normally only detect
         * interference after actions, not before. Further
         * CME-triggering checks apply to all other possible
         * violations of assumptions for example null or too-small
         * elementData array given its size(), that could only have
         * occurred due to interference.  This allows the inner loop
         * of forEach to run without any further checks, and
         * simplifies lambda-resolution. While this does entail a
         * number of checks, note that in the common case of
         * list.stream().forEach(a), no checks or other computation
         * occur anywhere other than inside forEach itself.  The other
         * less-often-used methods cannot take advantage of most of
         * these streamlinings.
         */

        private final ArrayListSource<E> list;
        private int index; // current index, modified on advance/split
        private int fence; // -1 until used; then one past last index
        private int expectedModCount; // initialized when fence set

        /**
         * Create new spliterator covering the given  range
         */
        ArrayListSpliterator(ArrayListSource<E> list, int origin, int fence,
                             int expectedModCount) {
            this.list = list; // OK if null unless traversed
            this.index = origin;
            this.fence = fence;
            this.expectedModCount = expectedModCount;
        }

        private int getFence() { // initialize fence to size on first use
            int hi; // (a specialized variant appears in method forEach)
            ArrayListSource<E> lst;
            if ((hi = fence) < 0) {
                if ((lst = list) == null) {
                    hi = fence = 0;
                } else {
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }

        @Override
        public ArrayListSource.ArrayListSpliterator<E> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                    new ArrayListSource.ArrayListSpliterator<>(list, lo, index = mid,
                            expectedModCount);
        }

        @Override
        public boolean tryAdvance(Consumer<? super E> action) {
            if (action == null) {
                throw new NullPointerException();
            }
            int hi = getFence(), i = index;
            if (i < hi) {
                index = i + 1;
                E e = (E) list.elementData[i];
                action.accept(e);
                if (list.modCount != expectedModCount) {
                    throw new ConcurrentModificationException();
                }
                return true;
            }
            return false;
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            int i, hi, mc; // hoist accesses and checks from loop
            ArrayListSource<E> lst;
            Object[] a;
            if (action == null) {
                throw new NullPointerException();
            }
            if ((lst = list) != null && (a = lst.elementData) != null) {
                if ((hi = fence) < 0) {
                    mc = lst.modCount;
                    hi = lst.size;
                } else {
                    mc = expectedModCount;
                }
                if ((i = index) >= 0 && (index = hi) <= a.length) {
                    for (; i < hi; ++i) {
                        E e = (E) a[i];
                        action.accept(e);
                    }
                    if (lst.modCount == mc) {
                        return;
                    }
                }
            }
            throw new ConcurrentModificationException();
        }

        @Override
        public long estimateSize() {
            return getFence() - index;
        }

        @Override
        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

    /**
     * AbstractListSource.Itr 的优化版本
     */
    private class Itr implements Iterator<E> {
        int cursor;                                                  // 要返回的下一个元素的索引
        int lastRet = -1;                                            // 返回的最后一个元素的索引； -1 如果没有
        int expectedModCount = modCount;                             // 数组被修改的次数

        @Override
        public boolean hasNext() {
            return cursor != size;
        }

        @Override
        public E next() {
            checkForComodification();

            int i = cursor;
            if (i >= size) {
                throw new NoSuchElementException();
            } else {
                Object[] elementData = ArrayListSource.this.elementData;
                if (i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
        }

        @Override
        public void remove() {
            if (lastRet < 0) {
                throw new IllegalStateException();
            }
            checkForComodification();

            try {
                ArrayListSource.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayListSource.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayListSource.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // 在迭代结束时更新一次以减少堆写入流量
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        /**
         * 检查数组是否被并发修改且发生异常
         */
        final void checkForComodification() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * AbstractListSource.ListItr 的优化版本
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        @Override
        public boolean hasPrevious() {
            return cursor != 0;
        }

        @Override
        public int nextIndex() {
            return cursor;
        }

        @Override
        public int previousIndex() {
            return cursor - 1;
        }

        @Override
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0) {
                throw new NoSuchElementException();
            }
            Object[] elementData = ArrayListSource.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        @Override
        public void set(E e) {
            if (lastRet < 0) {
                throw new IllegalStateException();
            }
            checkForComodification();

            try {
                ArrayListSource.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayListSource.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

    private class SubList extends AbstractListSource<E> implements RandomAccess {
        private final AbstractListSource<E> parent;            // 被截取的 list 数组
        private final int parentOffset;                        // 被截取的 list 数组的起始下标索引
        private final int offset;                              // 偏移量值大小
        int size;                                              // 截取后数组大小

        /**
         * 构造函数
         *
         * @param parent    被截取的 list 数组
         * @param offset    偏移量值大小
         * @param fromIndex 左边界起始索引(包含)
         * @param toIndex   右边界结束索引(不包含)
         */
        SubList(AbstractListSource<E> parent, int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.size = toIndex - fromIndex;
            this.offset = offset + fromIndex;
            this.modCount = ArrayListSource.this.modCount;
        }

        @Override
        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayListSource.this.elementData(offset + index);
            ArrayListSource.this.elementData[offset + index] = e;
            return oldValue;
        }

        @Override
        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayListSource.this.elementData(offset + index);
        }

        @Override
        public int size() {
            checkForComodification();
            return this.size;
        }

        @Override
        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        @Override
        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            E result = parent.remove(parentOffset + index);
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }

        @Override
        protected void removeRange(int fromIndex, int toIndex) {
            checkForComodification();
            parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);
            this.modCount = parent.modCount;
            this.size -= toIndex - fromIndex;
        }

        @Override
        public boolean addAll(Collection<? extends E> c) {
            return addAll(this.size, c);
        }

        @Override
        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize == 0) {
                return false;
            }

            checkForComodification();
            parent.addAll(parentOffset + index, c);
            this.modCount = parent.modCount;
            this.size += cSize;
            return true;
        }

        @Override
        public Iterator<E> iterator() {
            return listIterator();
        }

        @Override
        public ListIterator<E> listIterator(final int index) {
            checkForComodification();
            rangeCheckForAdd(index);
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;
                int lastRet = -1;
                int expectedModCount = ArrayListSource.this.modCount;

                @Override
                public boolean hasNext() {
                    return cursor != ArrayListSource.SubList.this.size;
                }

                @Override
                public E next() {
                    checkForComodification();
                    int i = cursor;
                    if (i >= ArrayListSource.SubList.this.size) {
                        throw new NoSuchElementException();
                    }
                    Object[] elementData = ArrayListSource.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    cursor = i + 1;
                    return (E) elementData[offset + (lastRet = i)];
                }

                @Override
                public boolean hasPrevious() {
                    return cursor != 0;
                }

                @Override
                public E previous() {
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0) {
                        throw new NoSuchElementException();
                    }
                    Object[] elementData = ArrayListSource.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    cursor = i;
                    return (E) elementData[offset + (lastRet = i)];
                }

                @Override
                public void forEachRemaining(Consumer<? super E> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = ArrayListSource.SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = ArrayListSource.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        consumer.accept((E) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                    checkForComodification();
                }

                @Override
                public int nextIndex() {
                    return cursor;
                }

                @Override
                public int previousIndex() {
                    return cursor - 1;
                }

                @Override
                public void remove() {
                    if (lastRet < 0) {
                        throw new IllegalStateException();
                    }
                    checkForComodification();

                    try {
                        ArrayListSource.SubList.this.remove(lastRet);
                        cursor = lastRet;
                        lastRet = -1;
                        expectedModCount = ArrayListSource.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                @Override
                public void set(E e) {
                    if (lastRet < 0) {
                        throw new IllegalStateException();
                    }
                    checkForComodification();

                    try {
                        ArrayListSource.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                @Override
                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        ArrayListSource.SubList.this.add(i, e);
                        cursor = i + 1;
                        lastRet = -1;
                        expectedModCount = ArrayListSource.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                final void checkForComodification() {
                    if (expectedModCount != ArrayListSource.this.modCount) {
                        throw new ConcurrentModificationException();
                    }
                }
            };
        }

        @Override
        public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new ArrayListSource.SubList(this, offset, fromIndex, toIndex);
        }

        private void rangeCheck(int index) {
            if (index < 0 || index >= this.size) {
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size) {
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
        }

        private String outOfBoundsMsg(int index) {
            return "Index: " + index + ", Size: " + this.size;
        }

        private void checkForComodification() {
            if (ArrayListSource.this.modCount != this.modCount) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public Spliterator<E> spliterator() {
            checkForComodification();
            return new ArrayListSource.ArrayListSpliterator<>(ArrayListSource.this, offset,
                    offset + this.size, this.modCount);
        }
    }
}